Conventionally, when an individual user uses a variety of services offered over a network such as the Internet, an authentication process is carried out to verify that the individual user is a legitimate user. In such an authentication process, authentication generally uses an ID and a password preset for each individual user. For this purpose, a network is provided with an authentication server for carrying out an authentication process.
Recently, using a digital signature technique, digital signature data unique to an individual user is attached to individual data. This digital signature data ensures that data utilized by an individual user is not tampered by outsiders or is not leaked to outsiders, so that confidential information can be safely handled over a network.
Meanwhile, with a digital signature, an individual user is identified in association with an authentication process at an authentication server, and as a result, history of each individual user is accumulated as information one after another in the authentication server every time an authentication process is performed. Therefore, private information such as which site individual users have accessed and which service they have used is accumulated in the authentication server. Thus, in terms of protection of personal information, great caution is given to prevent leakage of such information.
In order to solve accumulation of history information of individual users caused by the use of digital signatures, it is proposed to use a digital group signature, which is the extended digital signature.
When a digital group signature is used, an individual user transmits, to an authentication server, signature data that certificates that the individual user anonymously belongs to a particular group. The authentication server then verifies that the individual user belongs to a particular group without specifying the individual user from the received signature data. Therefore, while preventing fraud by an individual user who does not belong to a group, the authentication server authenticates an individual user without accumulating history information for each individual user.
For anonymous authentication in such a digital group signature, pairing computation is used.
Pairing computation uses a two-input and one-output function. For example, letting S be a rational point over a prime field Fp and Q be a rational point over a k-degree extension field Fpk, when the two rational points S and Q are input, an element z in the extension field F*pk is output. Moreover, pairing computation has a bilinear property such that when a times of the rational point S and b times of the rational point Q are input, the ab-th power of z is calculated. This bilinearity is utilized in authentication. Here, “k” is an embedding degree, and “F*pk” is, strictly speaking, expressed as:F*pk  [Formula 1]in mathematical representation, but is here represented as “F*pk” due to limitations in expression.
In general, for each of the rational points S, Q, a point on an elliptic curve is used. The pairing computation of a rational point on an elliptic curve includes a step of performing computation according to Miller's algorithm and a step of performing exponentiation on the computation result.
With a digital group signature, when access right of an individual user belonging to a group is authenticated, a pairing computation is first performed for excluding an individual user whose access right expires. Then, with the digital group signature, an authentication process is performed through a pairing computation for a predetermined individual user, so that an attribute change such as issue or expiration of access right for each individual user is flexibly handled.
Then, for example, in a case of a digital group signature for a group consisting of 10,000 individual users, if there are 100 individual users whose access rights expire, 100 pairing computations are required. At present, one pairing computation by a general electronic calculator requires about 0.1 second. Accordingly, 100 pairing computations require about 10 seconds. Therefore, in the present situation, a digital group signature scheme is not deemed to be practical and has not been widely used.
In the present situation, in order to put digital group signatures into practical use, researches are focused on improving the speed of pairing computations. For example, a technique for achieving fast pairing computations proposes using Tate pairing computation defined over an elliptic curve to reduce the computation load (see, for example, Patent Document 1).    Patent Document 1: Japanese Patent Application Publication No. 2005-316267